﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ClusterAggregation.Clusterers
{
    using Datum;
    using DataSets;
    /**
     * simple k-means
     */
    public class CKMeansImpl:IClusterer
    {
        /** private locking object, helps enforce re-entrability of functions. */
        private object m_lock = new object();
        /** private int, stores the number of clusters (k) */
        private int m_numberOfClusters = 3;
        /** boolean to help indicate if there was a change in the clustering between interations */
        private bool    m_notConverged;
        /** array of the center of clusters (centroids) */
        private AData[] m_clusterCentroids;
        /** this variable indicates the location of each datum (to which cluster the datum belongs) */
        private int[]   m_datumLocation;
        /** similarity (distance) function */
        private ISimilarity m_distanceFunction;
        /** the maximum number of iterations of the main loop in the K-Means implementation */
        private int m_maxIterations;
        /** number of objects in cluster*/
        private int[] m_objectsInCluster;
        /** Resamplings left of clusterings (in case of empty clusters) */
        private int m_resamplers;
      
        /**
        *  This function is the API to cluster data (arg) with the distance function (distFunc) into k different clusters.
        * 
        *  @param arg (AData) [IN], input data.
        *  @param distFunc (ISimilarity) [IN], the data will be clustered using this distance function.
        *  @param k (int) [IN], the number of clusterings.
        *  @return CPartition the clustered dataset as a partition.
        */    
        virtual public CPartition cluster(AData[] arg, ISimilarity distFunc, int k)
        {
            CPartition rez = new CPartition();
            rez.name = "K-Means";
            lock (m_lock)
            {
                // init class
                this.m_distanceFunction = distFunc;
                m_numberOfClusters = k;
                m_notConverged = true;
                m_clusterCentroids = new AData[k];
                m_datumLocation = new int[arg.Length];
                m_objectsInCluster = new int[k];
                m_resamplers = 3; //k;

                setRandomCenters(arg);

                for (int i = 0,j=0; (i < m_maxIterations) && j<5; i++)
                {
                    assignToClusteroids(arg);
                    recalculateCentroids(arg);

                    if (m_notConverged == false)
                        j++;
                    else
                        j = 0;
                } // end of main loop;

                // assign data to specific cluster
                assignData(arg,rez);

            } // end of lock
            return rez;
        } // end of function cluster

        /**
         * basic constructor
         * @param numOfIterations = 1500 (int) [IN] indicates the maximum number of iterations for k-means.
         */
        public CKMeansImpl(int numOfIterations = 1500)
        {
            m_maxIterations = numOfIterations;
        }

        /**
         * calculate centers of clusteroids
         * @param arg (AData[]) [IN]
         */
        public void recalculateCentroids(AData[] arg)
        {
            LinkedList<AData> tmp = new LinkedList<AData>();
            bool sampled = false ;

            for (int i = 0; i < m_clusterCentroids.Length; i++)
            {
                m_clusterCentroids[i].zerodize();
                m_objectsInCluster[i] = 0;
            }

            // calculate number of objects for each cluster
            for (int i = 0; i < arg.Length; i++)
            {
                m_objectsInCluster[m_datumLocation[i]]++;
            }

            // recalculate actual centers
            for (int i = 0; i < arg.Length; i++)
            {
                m_clusterCentroids[m_datumLocation[i]].accumulate(arg[i], m_objectsInCluster[m_datumLocation[i]]);
            }

            for (int i = 0; i < m_objectsInCluster.Length ; i++)
            {
                if (m_objectsInCluster[i] > 0)
                {
                    tmp.AddFirst(m_clusterCentroids[i]);
                }
            }

            if (m_resamplers > 0)
            {
                if (tmp != null)
                {
                    int j = 0;
                    AData[] cntroids = tmp.ToArray();
                    for (int i = 0; i < m_objectsInCluster.Length; i++)
                    {
                        if (m_objectsInCluster[i] == 0)
                        {
                            m_clusterCentroids[i].accumulate(cntroids[j], 0);
                            j = (j + 1) % cntroids.Length;
                            sampled = true;
                        }
                    }
                }
            }
            if (sampled)
            {
                m_resamplers = m_resamplers - 1;
            }
        }

        /**
         * recalculate clusteroids
         * @param arg (AData[]) [IN] 
         */
        private void assignToClusteroids(AData[] arg)
        {
            m_notConverged = false;
            int oldLocation;
            double minDistance;
            double tmpDistance;
            int bestFittedCentroid;

            // for each datum
            for (int i = 0; i < arg.Length; i++)
            {
                oldLocation = m_datumLocation[i];

                minDistance = m_distanceFunction.similarity(arg[i], m_clusterCentroids[0]);
                bestFittedCentroid = 0;

                // give a chance to each cluster
                for (int j = 1; j < m_numberOfClusters; j++)
                {
                    tmpDistance = m_distanceFunction.similarity(arg[i], m_clusterCentroids[j]);
                    if (tmpDistance < minDistance)
                    {
                        minDistance = tmpDistance;
                        bestFittedCentroid = j;
                    }
                }

                m_datumLocation[i] = bestFittedCentroid;

                // if location's changed even once, continue loop
                if (oldLocation != m_datumLocation[i])
                    m_notConverged = true;
            }            
        }

        /** 
         * this function assigns the data to it's specific clusters in the partition
         * @param arg (AData[]) [IN]
         * @oaram cont (CPartition) [OUT] new container for the clusteroids, container is in partition form.
         */
        private void assignData(AData[] arg,CPartition cont)
        {

            CCluster[] clusters = new CCluster[m_numberOfClusters];
            for (int i = 0; i < m_numberOfClusters; i++)
            {
                clusters[i] = new CCluster();
            } // finished allocating objects

            
            // assign each datum to selected cluster
            for (int i = 0; i < arg.Length; i++)
            {
                clusters[m_datumLocation[i]]._data.Add(arg[i]);
            }


            // add objects to container to create a partition (or clustering)
            for (int i = 0; i < m_numberOfClusters; i++)
            {
                cont._clusters.Add(clusters[i]);
            }
        }// end of assignData

        /**
         * this function sets random centers to clusteroids
         * @param arg (AData[]) [IN]
         */
        private void setRandomCenters(AData[] arg)
        {
            for (int i = 0; i < m_clusterCentroids.Length; i++)
            {
                m_clusterCentroids[i] = arg[0].getRandomDatum();
            }

        }// end of setRandomCenters

    }
}
